package top.minuy.structure.graph.cycle.bfs;

import top.minuy.structure.graph.representations.table.Graph;

import java.util.ArrayList;
import java.util.List;

/**
 * 环检测，广度优先遍历
 *
 * @author Minuy
 * @time 10:10
 * @date 2021/11/20
 */
public class CycleDetection {

    private Graph g;
    private boolean[] isVisited;
    private boolean hasCycle;

    public CycleDetection(Graph g) {
        this.g = g;

        if (g.isDirected()){
            throw new IllegalArgumentException("CycleDetection only works in undirected graph.");
        }

        isVisited = new boolean[g.V()];
        hasCycle = false;

        for (int v = 0; v < g.V(); v++) {
            if (!isVisited[v]) {
                if (bfs(v, v)) {
                    hasCycle = true;
                    break;
                }
                // System.out.println("根顶点："+v);
            }
        }
    }

    private boolean bfs(int v, int parent) {
        List<Integer> queue = new ArrayList<>();
        queue.add(v); // 根顶点入队
        isVisited[v] = true; // 入队的时候设置为true
        // System.out.println("根顶点入队："+v);
        // System.out.println("==============");
        while (!queue.isEmpty()) {
            // 第一个元素出队
            v = queue.remove(0);
            // System.out.println("第一个元素出队并访问："+v);

            // 访问
            // order.add(v);

            for (int w : g.adj(v)) {
                if (!isVisited[w]) {  // 如果没被访问过
                    queue.add(w);  // 入队
                    // System.out.println("子顶点入队："+w);
                    isVisited[w] = true; // 入队的时候设置为true
                } else if (w != parent) { // 子顶点已经被访问过了，且不是父顶点，则存在环
                    return true;
                }
            }
            parent = v;
        }
        return false;
    }

    /**
     * 获取是否有环
     *
     * @return boolean 是否有环
     * @author Minuy
     * @date 2021/11/20 10:14
     */
    public boolean hasCycle() {
        return hasCycle;
    }


    @Override
    public String toString() {
        return String.valueOf(hasCycle());
    }
}
